//
// Created by 许欣鑫 on 25-3-27.
//

#ifndef SOLUTION_1_3_H
#define SOLUTION_1_3_H
#include <vector>
using namespace std;

class solution_1_3 {
public:
    //最大子数组和 https://leetcode.cn/problems/maximum-subarray/
    int maxSubArrayPre(vector<int> &nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        vector pre_sum(n + 1, 0);
        int min_pre_sum = 0;
        int ans = INT_MIN;
        for (int i = 1; i < n + 1; i++) {
            pre_sum[i] = pre_sum[i - 1] + nums[i - 1];
            ans = max(ans, pre_sum[i] - min_pre_sum);
            if (min_pre_sum > pre_sum[i]) {
                min_pre_sum = pre_sum[i];
            }
        }
        return ans;
    }

    int maxSubArrayDP(vector<int> &nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        vector dp(n + 1, 0);
        for (int i = 1; i < n + 1; i++) {
            dp[i] = max(dp[i - 1], 0) + nums[i-1];
        }
        return *max_element(dp.begin(), dp.end());
    }
    //找到最大开销的子串 https://leetcode.cn/problems/find-the-substring-with-maximum-cost/description/
    int maximumCostSubstring(string s, string chars, vector<int>& vals) {

    }

};
#endif //SOLUTION_1_3_H
